package com.zhugang.week05;

/**
 * @program algorithms
 * @description: searchRange
 * @author: chanzhugang
 * @create: 2022/07/05 17:14
 */
public class SearchRange {

    public static void main(String[] args) {
        SearchRange searchRange = new SearchRange();
        int[] nums = new int[]{5, 7, 7, 8, 8, 10};
        int[] res = searchRange.searchRange(nums, 8);
        for (int index : res) {
            System.out.println(index);
        }
    }

    /**
     * 34 排序数组中查找元素的第一个和最后一个位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        // 抽象为查找第一个值等于给定元素的值 和 最后一个值等于给定元素的值 的下标，用数组返回
        // 第一个值等于给定元素的值下标
        int low = 0;
        int high = nums.length - 1;
        int left = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                // 是否是第一个值满足,向前探测
                if (mid == 0 || nums[mid - 1] != target) {
                    // 真命中
                    left = mid;
                    break;
                } else {
                    high = mid - 1;
                }
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        // 最后一个值等于给定元素的值下标
        low = 0;
        high = nums.length - 1;
        int right = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                // 是否是最后一个值满足，向后探测
                if (mid == nums.length - 1 || nums[mid + 1] != target) {
                    right = mid;
                    break;
                } else {
                    low = mid + 1;
                }
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return new int[]{left, right};
    }
}